package week02

// 1011. 在 D 天内送达包裹的能力
// https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/

func shipWithinDays(weights []int, days int) int {
	// 最小运输能力=最重的一个包裹的重量
	// 最大运输能力=所有包裹的重量
	var minTrans, maxTrans = 0, 0
	for _, weight := range weights {
		minTrans = max(minTrans, weight)
		maxTrans += weight
	}
	for minTrans < maxTrans {
		var trans = (maxTrans - minTrans) / 2 + minTrans
		if isValid(weights, days, trans) {
			maxTrans = trans
		} else {
			minTrans = trans + 1
		}
	}
	return maxTrans
}

func isValid(weights []int, days int, trans int) bool {
	var need = 1 // 需要多少天
	var sum = 0 // 总重量
	for _, weight := range weights {
		if sum+weight <= trans { // 在船的运输能力内
			sum += weight
		} else {
			need++
			sum = weight
		}
	}
	return need <= days
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}